package leetcode;

/**
 * 不用的二叉搜索树
 */
public class Solution43 {
    class Solution {
        public int numTrees(int n) {
            //创建dp数组
            int[] dp = new int[n+1];
            //进行初始化
            //3个节点  头1 = 左子0 + 右子2
            //头2 = 左子1 + 右子1
            //头3 = 左子0 + 右子2
            dp[0] = 1;
            dp[1] = 1;
            //遍历
            for(int i = 2;i <= n;i++){
                for(int j = 1;j <=i ;j++){
                    dp[i] += dp[j-1]*dp[i-j];
                }
            }
            return dp[n];
        }
    }
}
